Polynomial-time Algorithms for the Subset Feedback Vertex Set Problem on Interval Graphs and Permutation Graphs

摘要

Given a vertex-weighted graph $G=(V,E)$ and a set $S \subseteq V$, a subsetfeedback vertex set $X$ is a set of the vertices of $G$ such that the graphinduced by $V \setminus X$ has no cycle containing a vertex of $S$. The\textsc{Subset Feedback Vertex Set} problem takes as input $G$ and $S$ and asksfor the subset feedback vertex set of minimum total weight. In contrast to theclassical \textsc{Feedback Vertex Set} problem which is obtained from the\textsc{Subset Feedback Vertex Set} problem for $S=V$, restricted to graphclasses the \textsc{Subset Feedback Vertex Set} problem is known to beNP-complete on split graphs and, consequently, on chordal graphs. However as\textsc{Feedback Vertex Set} is polynomially solvable for AT-free graphs, nosuch result is known for the \textsc{Subset Feedback Vertex Set} problem on anysubclass of AT-free graphs. Here we give the first polynomial-time algorithmsfor the problem on two unrelated subclasses of AT-free graphs: interval graphsand permutation graphs. As a byproduct we show that there exists apolynomial-time algorithm for circular-arc graphs by suitably applying ouralgorithm for interval graphs. Moreover towards the unknown complexity of theproblem for AT-free graphs, we give a polynomial-time algorithm forco-bipartite graphs. Thus we contribute to the first positive results of the\textsc{Subset Feedback Vertex Set} problem when restricted to graph classesfor which \textsc{Feedback Vertex Set} is solved in polynomial time.